#include "kmp.h"
#include <cstring>

using namespace VLRTSP;

/**
 * @Author: CimZzz
 * @Date: 2022-01-12 09:59:22
 * 
 * 构造函数
 * @param matchBuf 匹配字节数组
 * @param length 字节数组长度
 */
KMP::KMP(uint8_t* matchBuf, uint32_t length) {
	this->nodes = new KMPNode[length];
	this->length = length;
	this->nodes[0].dpMap[matchBuf[0]] = 1;
	uint32_t prefixStack = 0;
	for(uint32_t i = 1 ; i < length ; i ++) {
		KMPNode prefixNode = this->nodes[prefixStack];
		uint8_t matchByte = matchBuf[i];
		this->nodes[i].dpMap.insert(prefixNode.dpMap.begin(), prefixNode.dpMap.end());
		this->nodes[i].dpMap[matchByte] = i + 1;
		std::map<uint8_t, uint32_t>::iterator iter = prefixNode.dpMap.find(matchByte);
		if(iter != prefixNode.dpMap.end()) {
			prefixStack = iter->second;
		} else {
			prefixStack = 0;
		}
	}
}


/**
 * @Author: CimZzz
 * @Date: 2022-01-12 11:21:31
 * 
 * 构造函数
 * @param matchBuf 通过字符串构造
 */
KMP::KMP(const char* matchBuf): KMP((uint8_t *)matchBuf, strlen(matchBuf)) {
}

/**
 * @Author: CimZzz
 * @Date: 2022-01-12 10:07:23
 * 
 * 析构函数
 */
KMP::~KMP() {
	delete [] this->nodes;
}

/**
 * @Author: CimZzz
 * @Date: 2022-01-12 10:08:41
 * 
 * 匹配字符串
 * @param matchBuf 用来进行匹配的原始字节数组
 * @param length 字节数组长度
 * @return 如果匹配成功，返回原始字节数组中匹配字节数组起始下标
 */
int64_t KMP::matchBefore(uint8_t* matchBuf, uint32_t length) {
	if(length < this->length) {
		return -1;
	}
	// pat 的初始态为 0
	int j = 0;
	for (int i = 0; i < length; i++) {
		KMPNode matchNode = this->nodes[j];
		// 计算 pat 的下一个状态
		std::map<uint8_t, uint32_t>::iterator iter = matchNode.dpMap.find(matchBuf[i]);
		if(iter != matchNode.dpMap.end()) {
			j = iter->second;
		} else {
			j = 0;
		}
		// 到达终止态，返回结果
		if (j == this->length) return i - this->length + 1;
	}
	// 没到达终止态，匹配失败
	return -1;
}

/**
 * @Author: CimZzz
 * @Date: 2022-01-12 10:08:41
 * 
 * 匹配字符串
 * @param matchBuf 用来进行匹配的原始字节数组
 * @param length 字节数组长度
 * @return 如果匹配成功，返回原始字节数组中匹配字节数组结束下标 + 1
 */
int64_t KMP::matchAfter(uint8_t* matchBuf, uint32_t length) {
	int64_t index = matchBefore(matchBuf, length);
	if(index == -1) {
		return index;
	}

	return index + this->length;
}